package com.zhongge.binarytreeOJ.question;


import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName MyBinTreeOfInt
 * @Description TODO
 * @Author zhongge
 * @Date 2025/9/2 20:57
 * @Version 1.0
 */
public class MyBinTreeOfInt {

    public static class TreeNode{
        public int val;
        public TreeNode left;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode right;

    }

    //二叉树的构建
    /**
     * 根据前序和中序构建 二叉树
     * @param preorder 前序
     * @param inorder 中序
     * @return 根节点
     */
    public TreeNode preAndInOfBuildTree(int[] preorder, int[] inorder) {
        //递归出口
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }
        //递归剪枝：没有
        //递归代码
        //1.前序==》先找到根
        int rootIndex = preorder[0];
        //创建根节点
        TreeNode root = new TreeNode(rootIndex);
        //2.有根找到根在中序中的位置，从而确定子树
        for (int i = 0; i < inorder.length; i++) {
            if (rootIndex == inorder[i]) {
                //确定左子树和右子树的个数
                //切割中序 从而得出中序左子树 和 右子树的个数
                int[] inLeft = Arrays.copyOfRange(inorder, 0, i);//下标顾前不顾后[0, i)==> [0, i - 1]
                int[] inRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);//下标顾前不顾后[i + 1, inorder.length)==>[i+1, inorder.length-1]

                //那么根据中序中的左右子树个数将前序左右子树也要进行相应的切割 从而进行左右子树的树的构建
                int[] preLeft = Arrays.copyOfRange(preorder, 1, inLeft.length + 1);//从1开始向后数中序子树的个数(因为前序和中序个数一定是相同的)
                //[1, inLeft.length + 1)==>[1, inLeft.length]==》下标到达(1 + inLeft.length)
                //那么下一次就从(1 + inLeft.length)开始  （这一步最好的办法就是画图理解）
                int[] preRight = Arrays.copyOfRange(preorder, inLeft.length + 1, preorder.length);//从左子树向后遍历后的下标开始 到 前序的最后一个下标

                //递归构建左右子树
                root.left = preAndInOfBuildTree(preLeft, inLeft);//前序的左子树和中序的左子树==》构建左子树的树
                root.right = preAndInOfBuildTree(preRight, inRight);//前序的右子树和中序的右子树==》构建左子树的树

                break;//找到就没必要往后找了（一定是找得到的）
            }
        }
        //递归的归
        return root;
    }

    /**
     * 根据中序和后序创建二叉树
     * @param inorder 中序
     * @param postorder 后序
     * @return 根节点
     */
    public TreeNode inAndPostOfBuildTree(int[] inorder, int[] postorder) {
        //递归出口
        if (inorder.length == 0 || postorder.length == 0) {
            return null;
        }
        //递归剪枝：没有
        //递归代码
        //1.后序==》先找到根
        int rootIndex = postorder[postorder.length-1];
        //创建根节点
        TreeNode root = new TreeNode(rootIndex);
        //2.由根找到根在中序中的位置，从而确定子树
        for (int i = 0; i < inorder.length; i++) {
            if (rootIndex == inorder[i]) {
                //确定左子树和右子树的个数
                //切割中序 从而得出中序左子树 和 右子树的个数
                int[] inLeft = Arrays.copyOfRange(inorder, 0, i);//下标顾前不顾后[0, i)==> [0, i - 1]
                int[] inRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);
                //下标顾前不顾后[i + 1, inorder.length)==>[i+1, inorder.length-1]

                //那么根据中序中的左右子树个数将 后序左右子树也要进行相应的切割 从而进行左右子树的树的构建

                //从0开始向后数中序子树的个数(因为前序和中序个数一定是相同的)
                int[] postLeft = Arrays.copyOfRange(postorder, 0, inLeft.length);

                //从nLeft.length开始向后数 到 前序的最后一个下标的前一个(因为最后一个是根节点)
                int[] postRight = Arrays.copyOfRange(postorder, inLeft.length, postorder.length - 1);

                //递归构建左右子树
                root.left = inAndPostOfBuildTree(inLeft, postLeft);//中序的左子树和后序的右子树==》构建左子树的树
                root.right = inAndPostOfBuildTree(inRight, postRight);//中序的右子树和后序的右子树==》构建左子树的树

                break;//找到就没必要往后找了（一定是找得到的）
            }
        }
        //递归的归
        return root;
    }


    //二叉树的遍历：
    /**
     * 层序遍历
     * @param root 根节点
     */
    public void levelOrder(MyBinTree.TreeNode root) {
        //队列
        Queue<MyBinTree.TreeNode> queue = new LinkedList<>();

        //初步的时候跟入队
        queue.offer(root);

        while (!queue.isEmpty()) {
            //出父 入儿子
            MyBinTree.TreeNode parent = queue.poll();
            System.out.print(parent.val + " ");

            if (parent.left != null) {
                queue.offer(parent.left);
            }

            if (parent.right != null) {
                queue.offer(parent.right);
            }
        }
        System.out.println();
    }

    /**
     * 中序遍历
     * @param root 根节点
     */
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }


    public static void main(String[] args) {
        MyBinTreeOfInt tree = new MyBinTreeOfInt();
        int[] inOrder = {9,3,15,20,7};
        int[] postOrder = {9,15,7,20,3};
        TreeNode treeNode = tree.inAndPostOfBuildTree(inOrder, postOrder);

        //遍历
        tree.inOrder(treeNode);
    }
}
